//#include <string.h>
#include <Windows.h>
#include<stdio.h>
struct huffmanNode
{
	int weight;
	int llink;//-1时说明该分支没孩子
	int rlink;//-1时说明该分支没孩子
	int flink;//父结点，为-1时说明是根
};

struct code
{
	int bit[256];//对于灰度图像，最多256个统计值，最多有256的编码    
	int start;
};

//创建huffman树，weightArray输入权重数组，n是待编码的序列长度
huffmanNode * creatHuffmanTree(int weightArray[256], int n)
{
	int i, j;
	int min1, min2, x1, x2;//每次记录最小的两个权重及其对应的数组下标
	//二叉树性质，任意一棵二叉树,度为0的结点总是比度为2的结点多一个  
	huffmanNode *HuffTree = new huffmanNode[2 * n - 1];
	//把叶子结点进数组，完成初始化
	for (i = 0; i<2 * n - 1; i++) {
		if (i<n)
			HuffTree[i].weight = weightArray[i];
		else
			HuffTree[i].weight = 0;
		HuffTree[i].llink = -1;
		HuffTree[i].rlink = -1;
		HuffTree[i].flink = -1;
	}

	int max = 0;//用这个数每次找树里面最小时的初始化，
	for (i = 0; i<n; i++) 
		max += weightArray[i];
	 /* 循环构造 Huffman 树 */
	for (i = 0; i<n - 1; i++) {//填制后边的非叶结点
		min1 = min2 = max;    /* min1、min2中存放两个无父结点且结点权值最小的两个结点 */
		x1 = x2 = 0;  /* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 */
		for (j = 0; j<n + i; j++) {
			if (HuffTree[j].weight<min1 && HuffTree[j].flink == -1) {
				min2 = min1;
				x2 = x1;
				min1 = HuffTree[j].weight;
				x1 = j;
			}
			else if (HuffTree[j].weight < min2 && HuffTree[j].flink == -1) {
				min2 = HuffTree[j].weight;
				x2 = j;
			}
		}/* end for */
		 /* 设置找到的两个子结点 x1、x2 的父结点信息 */
		HuffTree[x1].flink = n + i;
		HuffTree[x2].flink = n + i;
		HuffTree[n + i].weight = HuffTree[x1].weight + HuffTree[x2].weight;
		HuffTree[n + i].llink = x1;//小的放在前边，大的放在后边
		HuffTree[n + i].rlink = x2;
	} /* end for */
	return HuffTree;
}


//栈结构实现霍夫曼树的前序遍历，根，左，右，用来验证
void preOrder_HuffTree(huffmanNode *T, int n)
{
	struct huffmanNode s[100], t;
	int top = -1;
	if (n == 0)
		return;
	top = 0;
	s[top] = T[n - 1];//根结点进栈
	while (top>-1) {
		t = s[top];
		top--;
		printf("%3d", t.weight);//打印结点
		if (t.rlink != -1) {//右子树进栈
			top++;
			s[top] = T[t.rlink];
		}
		if (t.llink != -1) {//左子树进栈
			top++;
			s[top] = T[t.llink];
		}
	}
}


//n个叶结点，huffmanTree树上一共有2n-1个点，//只有前n个点需要编码，
void coding(huffmanNode *HuffTree, code *huffmanCode, int n)
{
	code cd;//中间变量
	int i, j, p, c;
	for (i = 0; i<n; i++) {
		cd.start = n - 1; //从最后一个位置记录      
		c = i; //c是当前结点的数组下标，p是其父结点
		p = HuffTree[c].flink;
		while (p != -1) {   /* 父结点存在 */
			if (HuffTree[p].llink == c)
				cd.bit[cd.start] = 0;//左子树0
			else
				cd.bit[cd.start] = 1;//右子树1
			cd.start--; /* 求编码的低一位 */

			//设置新的当前结点和其父结点，向树根回退
			c = p;
			p = HuffTree[c].flink;    /* 设置下一循环条件 */
		} /* end while */

		  /* cd里存放了当前叶结点的编码，保存到编码数组，记录其哈夫曼编码和编码的起始位 */
		cd.start++;//真正的起始位置
		for (j = cd.start; j<n; j++) {
			huffmanCode[i].bit[j] = cd.bit[j];
		}
		huffmanCode[i].start = cd.start;//真正的起始位置
	}
}

//对应每个权值的编码结果显示，T哈夫曼树的数组，huffmanCode对应的编码
void show_HuffCode(huffmanNode *T, code *huffmanCode, int n)
{
	int i, j;
	for (i = 0; i<n; i++) {
		printf("%d 's Huffman code is: ", T[i].weight);
		for (j = huffmanCode[i].start; j < n; j++) {
			printf("%d", huffmanCode[i].bit[j]);
		}
		printf("\n");
	}
}

//以下是图像编码部分
//统计图像中实际的灰度级及其对应权重，realGrayIndex存放实际非零灰度级的索引值, realGrayWeight对应的频率或权重，realGrayNum非0灰度个数，也是前边两数组长度
void calculateRealGray(unsigned char *imgBuf, int width, int height, unsigned char realGrayIndex[], int realGrayWeight[], int *realGrayNum)
{
	int i, j, hist[256] = { 0 };
	for (i = 0; i<height; i++) {//统计直方图
		for (j = 0; j<width; j++) {
			hist[*(imgBuf + i*width + j)]++;
		}
	}
	for (i = 0; i < 256; i++)//统计频率/权重
		realGrayWeight[i] = 0;
	int count = 0;
	for (i = 0; i < 256; i++) {//统计频率不为0的灰度级，用来生成哈夫曼树
		if (hist[i] != 0) {
			realGrayIndex[count] = i;
			realGrayWeight[count] = hist[i];
			count++;
		}
	}
	*realGrayNum = count;//实际灰度级数目
}

//哈夫曼编码并写成文件
void generateFile(unsigned char *imgBuf, int width, int height, char *fileout)
{
	//统计图像中频率非0的灰度级及其权重
	unsigned char realGrayIndex[256];
	int realGrayWeight[256], realGrayNum;
	calculateRealGray(imgBuf, width, height, realGrayIndex, realGrayWeight, &realGrayNum);

	//创建哈夫曼树并生成编码数组
	struct huffmanNode *HuffTree = creatHuffmanTree(realGrayWeight, realGrayNum);//创建huffman树
	struct code huffmanCode[256];//存放哈夫曼编码
	coding(HuffTree, huffmanCode, realGrayNum);//编码n个叶结点，huffmanTree树上一共有2n-1个点

	//创建文件
	FILE * fp;
	fp=fopen(fileout, "wb");
	fwrite(&realGrayNum, sizeof(int), 1, fp);//将实际有灰度级数写入文件
	fwrite(realGrayIndex, sizeof(char), realGrayNum, fp);//实际灰度级索引数组写文件
	fwrite(HuffTree, sizeof(huffmanNode), 2 * realGrayNum - 1, fp);//huffman树写入文件
	//图像宽、高写进文件，解码时才能申请合适的数据空间
	fwrite(&width, sizeof(int), 1, fp);
	fwrite(&height, sizeof(int), 1, fp);

	//对每一个字符编码写入的过程
	int i, j, k, t1, t2;
	char codebuf;//编码缓冲区
	t1 = 0;//缓冲区内编码位置
	for (i = 0; i < height; i++) {
		for (j = 0; j < width; j++) {
			//找到对应灰度级和权重
			for (k = 0; k < realGrayNum; k++) {
				if (realGrayIndex[k] == imgBuf[i*width + j])
					break;
			}
			for (t2 = huffmanCode[k].start; t2 < realGrayNum; t2++) {//编码序列依次写入缓冲区
				if (huffmanCode[k].bit[t2] == 0)
					codebuf &= ~(1 << t1);//编码位置置0
				else
					codebuf |= (1 << t1);//编码位置置1
				t1++;
				if (t1 == 8) {//编码缓冲区满，写入文件
					fwrite(&codebuf, sizeof(char), 1, fp);
					t1 = 0;
				}
			}
			if (i == height - 1 && j == width - 1) {//到了最后一个像素
				if (t1 != 0)//最后一次缓冲区还没填满，写入文件，结束循环
					fwrite(&codebuf, sizeof(char), 1, fp);
			}
		}//j
	}//i
	fclose(fp);
}



// 给定一个图像文件及其路径，读入图像数据。
unsigned char *readBmp(char *bmpName, int *width, int *height, int *byteCount)
{
	FILE *fp;
	fp=fopen( bmpName, "rb");
	if (fp == 0) return 0;
	fseek(fp, sizeof(BITMAPFILEHEADER), 0);

	int w, h, b;
	BITMAPINFOHEADER head;
	fread(&head, sizeof(BITMAPINFOHEADER), 1, fp);
	w = head.biWidth;
	h = head.biHeight;
	b = head.biBitCount / 8;
	int lineByte = (w * b + 3) / 4 * 4;

	if (b == 1)
		fseek(fp, 1024, 1);
	unsigned char *imgBuf = new unsigned char[w * h * b];
	for (int i = 0; i<h; i++)
	{
		fread(imgBuf +(h-1-i)*w*b, w*b, 1, fp);
		fseek(fp, lineByte - w*b, 1);
	}
	fclose(fp);

	*width = w, *height = h, *byteCount = b;

	return imgBuf;
}


int main()
{
	//创建huffman树
/*	int weightArray[256] = { 6,2,3,4,10,15 }, n = 4;
	struct huffmanNode *HuffTree=creatHuffmanTree(weightArray, n);//创建huffman树
	printf("前序遍历哈夫曼树：");
	preOrder_HuffTree(HuffTree, 2*n-1);
	printf("\n");

	struct code huffmanCode[256];//存放霍夫曼编码
	coding(HuffTree, huffmanCode, n);//编码n个叶结点，huffmanTree树上一共有2n-1个点
	printf("打印每个结点的编码：\n");
	show_HuffCode(HuffTree, huffmanCode, n);//显示
	 */ 

    char *bmpName = "D:\\教学相关\\数据结构\\数据结构2023\\第6章二叉树\\第三次课\\450-600.bmp";
    int width, height,byteCount;
    unsigned char *imgBuf=readBmp(bmpName, &width, &height, &byteCount);
    //哈夫曼编码并写成文件
    char *fileout= "D:\\教学相关\\数据结构\\数据结构2023\\第6章二叉树\\第三次课\\450-600.huff";
    generateFile(imgBuf, width, height, fileout);
     

	
/*	
	char c='a';
	int i=5;
	c &= ~(1 << i);//i位置0
	c |= (1 << i);//i位置1
	for (i = 0; i < 8; i++) {//按位输出
    	int t = (c & 1 << i) != 0;
    	printf("%d", t);
	}
*/	
     return 0;
}
